package code1;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/16 14:27
 * 基础快排--debug
 */
public class QuickSortDebug {

    public static <E extends Comparable<E>>  void sort(E[] arr) {
        int depth = 0;
        String depthString = generateDepthString(depth);
        System.out.print(depthString);
        System.out.println(String.format("quicksort arr[%d, %d]",0,arr.length-1));
        quicksort(arr,0,arr.length-1,depth);
    }


    public static <E extends Comparable<E>>   void quicksort(E[] arr,int left,int right,int depth){

        if(left > right) {
            return; //递归出口
        }
        String depthString = generateDepthString(depth);
        System.out.print(depthString);
        System.out.println(String.format("quicksort arr[%d, %d]",left,right));
        int p=partition(arr,left,right);

        System.out.print(depthString);
        System.out.println(String.format("quicksort arr[%d, %d]",left,right));
        quicksort(arr,left,p-1,depth+1);

        System.out.print(depthString);
        System.out.println(String.format("quicksort arr[%d, %d]",left,right));
        quicksort(arr,p+1,right,depth+1);


    }

    private static<E extends Comparable<E>> int partition(E[] arr, int left, int right) {

        E v = arr[left];
        int j  = left;
        for (int i = left+1; i <= right;i++ ) {
            if (arr[i].compareTo(v) < 0){
                j++;
                exchange(arr,i,j);
            }
//            大于就直接i++
        }
        //最后交换
        exchange(arr,left,j);

        return j;

    }

    private static  <E extends Comparable<E>> void exchange(E[] arr, int i, int j) {
        E temp=arr[i];
        arr[i] =arr[j];
        arr[j] = temp;
    }

    private static String generateDepthString(int depth){
        StringBuilder res = new StringBuilder();
        for (int i = 0; i <depth ; i++) {
            res.append("--");
        }
        return res.toString();
    }


    public static void main(String[] args) {
        Integer[] arr={4,6,5,2,3,8,7,1};
        QuickSortDebug.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+ " ");
        }
        System.out.println();


        int n = 100000;
        Integer[] array = ArrayGenerator.generateRandomArray(n, n);
        SortHelper.sortTest("QuickSort",array);
    }


}
